#include <iostream>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N=110;
ll dis[N];
bool cmp(pll a,pll b)
{
	return a.second<b.second;
}
int main()
{
	int n,m;
	cin>>n>>m;
	vector<pll> v[n];
	memset(dis,-1,sizeof(dis));
	for(int i=0;i<m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		a--,b--;
		v[a].push_back({b,c});
		v[b].push_back({a,c});
	}
	priority_queue<pll,vector<pll>,greater<pll> > q;
	q.push({0,0});
	vector<int> a;
	while(q.size())
	{
		ll d=q.top().first;
		ll x=q.top().second;

		q.pop();
		if(dis[x]!=-1) continue;
		dis[x]=d;
		a.push_back(x);
		if(x==n-1) break;
		for(auto it:v[x])
		{
			q.push({d+it.second,it.first});
		}
	}
	if(dis[n-1]==-1)
	{
		cout<<"inf";
		return 0;
	}
	cout<<dis[n-1]<<' '<<a.size()-1<<endl;
	string s(n,'0');
	for(int i=0;i<a.size()-1;i++)
	{
		s[a[i]]='1';
		cout<<s<<' '<<dis[a[i+1]]-dis[a[i]]<<endl;
	}
	
	return 0;
}

